package com.hqq.exercise.divide_conquer;

/**
 * BinarySearch 二分搜索
 * Created by heqianqian on 2017/8/28.
 */
public class BinarySearch {

    public static void main(String[] args) {
        /*二分查找*/
        int[] array = new int[]{1, 2, 2, 4, 5};
        int index = binarySearch(array, 2);
        System.out.println(index);

        /*二分查找变种*/
        /*第一个等于num的数*/
        array = new int[]{2, 2, 2, 4, 5};
        index = binarySearchFirstEquals(array, 2);
        System.out.println(index);
        /*最后一个等于num的数*/
        array = new int[]{2, 2, 1, 2, 2};
        index = binarySearchLastEquals(array, 2);
        System.out.println(index);
        /*最后一个小于等于num的数*/
        array = new int[]{1, 10, 30, 50, 60};
        index = binarySearchLastLessOrEquals(array, 20);
        System.out.println(index);
        /*最后一个大于num的数*/
        array = new int[]{1, 10, 30, 50, 60};
        index = binarySearchFirstMore(array, 40);
        System.out.println(index);
    }

    /**
     * 普通的二分查找
     */
    public static int binarySearch(int[] array, int num) {
        int left = 0, right = array.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] == num) {
                return mid;
            } else if (array[mid] < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 二分查找变种
     * 要求找到第一个等于num的数
     */
    public static int binarySearchFirstEquals(int[] array, int num) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException();
        }
        int left = 0, right = array.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] >= num) {
                //当前元素和目标元素相等时 也会在前一半数组进行查找 以确保找到第一个等于num的元素
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (left < array.length && array[left] == num) {
            return left;
        }
        return -1;
    }

    /**
     * 二分查找变种
     * 要求找到最后一个等于num的数
     */
    public static int binarySearchLastEquals(int[] array, int num) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException();
        }
        int left = 0, right = array.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid]>num){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        if (right < array.length && array[right] == num) {
            return right;
        }
        return -1;
    }

    /**
     * 二分查找变种
     * 查找最后一个等于或者小于key的元素
     */
    public static int binarySearchLastLessOrEquals(int[] array, int num) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException();
        }
        int left = 0, right = array.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }

    /**
     * 二分查找变种
     * 查找最后一个大于key的元素
     */
    public static int binarySearchFirstMore(int[] array, int num) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException();
        }
        int left = 0, right = array.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] >= num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
